/**
 * 2个条件：
 * 1. 回文
 * 2. 数字k恰好出现k次
 * 
 * 求比N大的最小的满足条件的数
 * 显然用二分，在实现数位DP的基础上
 * 
 * 用map到一半就会T，用gp_hash_table还有10个左右会T
 * 再随便剪一下枝即可
 */
#include <bits/stdc++.h>
#include <bits/extc++.h>
using namespace std;

#define ONLINE_JUDGE
#ifndef ONLINE_JUDGE
#else
#define printf _null_func_
#endif

void _null_func_(...){}

using llt = long long;
const llt MOD = 1E9 + 7;

int const FULL = 10; // 进制
vector<int> G;

struct _t{
    int already;        // 已填充长度
    int largerInLow;    // 低位是否已超出
    array<int, 10> cnt; // 已填充的各数字的数量
    int sz;             // cnt中的非零数量，冗余数据
    _t():already(0),largerInLow(0),cnt{0}, sz(0){}
    bool operator < (const _t & right) const {
        if(already != right.already) return already < right.already;
        if(largerInLow != right.largerInLow) return largerInLow < right.largerInLow;
        for(int i=0;i<10;++i){
            if(cnt[i] != right.cnt[i]) return cnt[i] < right.cnt[i];
        }
        return false;
    }
    string toString()const{
        string ans;
        ans += "already = " + to_string(already) + ", ";
        ans += "larger = " + to_string(largerInLow) + ", ";
        ans += "cnt = {";
        for(int i=0;i<10;++i){
            if(cnt[i]){
                ans += to_string(i) + ": " + to_string(cnt[i]) + ", ";
            }
        }
        ans += "}";
        return ans;
    }
    // 相当于剪枝条件
    bool maybeOK() const {
        // 最多5个不同的数
        if(sz > 5) return false;
        if(cnt[9]){ // 如果有9
            // 8和7不能与9同时出现
            if(cnt[8] or cnt[7] or sz > 4) return false;
        }
        if(cnt[8]){
            if(sz > 4) return false;
            if(cnt[7] and sz > 2) return false;
            if(cnt[6] and sz > 3) return false;
            if(cnt[5] and sz > 3) return false;
            if(cnt[4] and sz > 4) return false;
        }
        if(cnt[7]){
            if(sz > 4) return false;
        }
        return true;
    }
};

template<>struct std::tr1::hash<_t>{
    static std::size_t splitmix64(std::size_t x){
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);        
    }

    std::size_t operator () (const _t & t) const {
        static const std::size_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        std::size_t ans = FIXED_RANDOM;
        ans = splitmix64(ans + t.already);
        ans = splitmix64(ans + t.largerInLow);
        for(auto i : t.cnt) {
            ans = splitmix64(ans + i); // 也有用异或的
        }
        return ans;    
    }
};

template<>struct std::equal_to<_t>{
    bool operator () (const _t & a, const _t & b) const {
        if(a.already != b.already) return false;
        if(a.largerInLow != b.largerInLow) return false;
        for(int i=0;i<10;++i){
            if(a.cnt[i] != b.cnt[i]) return false;
        }
        return true;        
    }
};

// array<map<_t, llt>, 18> D;
array<__gnu_pbds::gp_hash_table<_t, llt>, 18> D;

// state表示到当前为止的状态
llt dfs(int pos, _t state, bool lead, bool limit){
    if(pos < state.already){
        // 如果高位受限且低位超出，直接返回0
        if(limit and state.largerInLow) return 0;
        // 否者检查cnt
        for(int i=0;i<10;++i)if(state.cnt[i]!=0 and state.cnt[i]!=i) {
            return 0;
        }
        return 1;
    }

    if(not lead and not limit){
        auto it = D[pos].find(state);
        if(it != D[pos].end())
        {
            return it->second;
        }
    }

    int last = limit ? G[pos] : FULL - 1;
    llt ans = 0;

    for(int i=0;i<=last;++i){
        if(0 == i && lead){
            ans += dfs(pos - 1, _t(), true, limit&&i==last);
            continue;
        }
        // 否则要取出对称位置
        int duicheng = state.already;
        int bitInLowHalf = G[duicheng];
        // 确定新的largerInLow，三种可能
        int nLarger = 0;
        if(bitInLowHalf < i) nLarger = 1; // 显然比原数要大
        else if(bitInLowHalf == i) nLarger = state.largerInLow; // 显然与参数保持一致
        else ; // do nothing, 为0, 即使之前有Larger现在也要取消
        // 确定新状态
        _t nState = state;
        nState.already += 1;
        nState.largerInLow = nLarger;
        if(duicheng == pos) nState.cnt[i] += 1;
        else nState.cnt[i] += 2; // 一次填充2个i
        if(state.cnt[i] == 0) nState.sz = state.sz + 1;
        else nState.sz = state.sz;
        // 相当于剪枝
        if(nState.cnt[i] <= i and nState.maybeOK()){
            ans += dfs(pos - 1, nState, false, limit&&last==i);     
        }
           
    }
    if(not lead and not limit){
        D[pos].insert({state, ans});
    }
    // printf("return ans = %lld;\n", ans);
    return ans;
}

llt digitDP(llt n){
    G.clear();
    while(n){
        G.emplace_back(n % FULL);
        n /= FULL;
    }
    auto tmp = dfs(G.size() - 1, _t(), true, true);
    return tmp;
}

class Solution {
public:
    long long specialPalindrome(long long n) {
        auto target = digitDP(n);
        // return target;
        llt left = 1, right = 1E16, mid;
        do{
            mid = (left + right) >> 1;
            auto tmp = digitDP(mid);
            if(tmp <= target) left = mid + 1;
            else right = mid - 1;
        }while(left <= right);   
        return left; 
    }
};

